1. Field of the Invention
The invention relates to the field of automated design of asynchronous digital circuits, and in particular to an apparatus and methodology for designing asynchronous and combinations of synchronous and asynchronous circuits.
2. Description of the Prior Art
Asynchronous logic circuits are present in and critical in the design of low power, delay sensitive, high performance digital circuits. Typically, asynchronous logic circuits are used in real time applications involving digital communication and computer systems. Although there are some automated methodologies which can provide machine design of some types of asynchronous circuits, heretofore no practical automated methodology has existed which could successfully provide design solutions for real applications. Therefore, the solution of complex asynchronous circuit design problems always required intuition and experience, and was consequently a difficult and error prone task. Often the design of the asynchronous circuit entails a substantial amount of time to debug. What is needed is an adequate synthesis method which will simplify design and reduce errors.
Asynchronous interface circuits as used in real time digital systems, combined various microprocessors, memories and other asynchronous interface circuits, each of which either operate at different clock rates or asynchronously from each other. Prior art attempts to devise a general solution resulted in the development of an event-based graphically specification, called a signal transition graph (STG). See Tam-Anh Chu, "Synthesis of Self-Timed VLSI Circuits from Graph Theoretic Specifications," PhD Thesis, Department of Electrical Engineering and Computer Science, MIT, June 1987, and a direct synthesis method as shown in Chu, supra; Lavagno et al., "Algorithms for Synthesis of Hazard-Free Asynchronous Circuits," Proc. of 28th DAC, at 302-08 (1991); Vanbekbergen et al., "Optimized Synthesis of Asynchronous Control Circuits front Graph Theoretic Specifications," IEEE Trans. on CAD, 11(11):1426-38 (1992); and Yu et al., "A New Approach for Checking Unique State Coding Property of Signal Transition Graphs," Proc. of EDAC, at 312-21 (1992). These prior attempts were inadequate to synthesize complex designs involving a large number of constraints.
The prior art methods were limited by the types of asynchronous behavioral specifications that could be synthesized. For example, some prior art techniques as described by Lin, "Automatic Synthesis of Asynchronous Circuits," Proc. of 28 DAC at 296-301 (1991), Vanbekbergan and Yu each propose synthesis techniques which are restricted to STG graphs which describe only concurrent asynchronous behavior. These prior art techniques were also limited by the additional restriction that every signal could only have one rising and one falling transition. Lavagno et al., "Solving the State Assignment Problem for Signal Transition Graphs," Proc. 29th DAC at 568-72 (1992), proposed a synthesis methodology from STG specifications with a limited interplay of concurrency and choice. The signal transition graph was solved by transforming it into a finite state machine state table.
The synthesis problem was solved with state minimization as shown by Puri and Gu, "An Efficient Algorithm to Search for Minimal Closed Covers in Sequential Machines," IEEE Transactions on CAD, 12(6):737-45 (1993) and with critical hazard-free state assignment techniques, as shown by Tracey, "Internal State Assignment for Asynchronous Sequential Machines," IEEE Trans. on Computers 15(4):551-60 (1966). Still, the state coding solutions obtained by this methodology corresponded only to a special class of STG transformations. Vanbekbergen et al., "A Generalized State Assignment Theory for Transformations on Signal Transition Graphs," Proc. of ICCAD at 112-17 (1992), provided a solution to the state coding problem for general STG specifications which was not limited to only concurrent and synchronous behavior or safe flee-choice Petri nets. The state coding problem was, thus, formulated as a Boolean satisfiability (SAT) problem. Unfortunately, Boolean formula derived from practical signal transition graphs are too large to be efficiently solved. For example, a moderately sized signal transition graph with 174 states results by this methodology in a Boolean formula with 35,386 clauses and 1,044 signal variables. It usually takes prohibitively long times to find a satisfiable assignment for such a very large Boolean formula. In many cases, the formulas could only be solved by utilizing some human insight into the structure of the problem. What is needed is a solution which can be produced through automated software by machine without these disadvantages.
Dangelo et al., "Methodology for Deriving Executable Low-Level Structural Descriptions and Valid Physical Implementations of Circuits and Systems from High-Level Semantic Specifications and Descriptions Thereof," U.S. Pat. No. 5,222,030 (1993) shows in connection with FIG. 2 a methodology utilizing a partition step 3 which simplifies overall synthesis, analysis and verification tasks by breaking the design into separate modules. Consulting package requirements, input/output capabilities, and other technological dependent information bearing on the design and process yields are used to form optimally partitioned modules. For each partition module, the modular description step 4 generates the register transfer level description within the set of timing and area design constraints accompanying that particular module. The design constraints are related only to that module's domain. The module descriptions which are generated are then examined, verified and combined in composition step 5 in order to reconstruct the design that will ultimately be synthesized.
Maki et al., "Method for Designing Pass Transistor Asynchronous Sequential Circuits," U.S. Pat. No. 4,912,348 (1990) describes a method for designing pass transistor asynchronous sequential circuits wherein each pass transistor path of the circuit's state variables to a stable state under a given input signal is separately partitioned. The approach is essentially to avoid critical race conditions between the circuit state variables by employing state assignments in which the transition paths between the states are disjoint. Partitioning enables a transition path consisting of all the states that the circuit could assume in transition between an unstable state and a stable state for given input to be separately realized. Principle steps in the methodology include generating a flow table representing the desired circuit characteristics, coding the flow table with state assignments, generating partitions of the circuits internal states for each input variable, generating a product expression for each partition, and combining the partitions to construct the overall circuit.
Kaplan, "Optimal Integrated Circuit Generation," U.S. Pat. No. 5,237,513 (1993) describes a method for optimal generation of integrated circuits. The method generates an integrated circuit structure necessary to perform a specific function by separately developing a set of combinatorial logic gates. The logic gates when combined perform the specified function. The method first breaks down the circuit's Boolean logic expression into a number of multidimensional Boolean spaces, which represent the inputs and outputs of the circuit's function. These spaces are then separately manipulated to generate a corresponding set of paths from which logic transistor networks are formed to provide the overall circuit structure. This results in an integrated circuit having smaller area and possibly faster operation.
McDermith et al., "Partitioning of Boolean Logic Equations into Physical Logic Devices," U.S. Pat. No. 5,140,526 (1992) describes a method and apparatus for partitioning Boolean equations in order that physical logic devices for those equations can be implemented within the user's design constraints. Based on the user-generated cost values, physical constraints and pin directives, the partitioning process 340 of FIG. 3 generates a plurality of possible partitioning solutions for implementation. Such solutions include the actual information necessary to configure or connect devices to generate the desired logical operations.
Poirot et al., "Method and Apparatus for the Design and Fabrication of Integrated Circuits Employing Logic Decomposition Algorithms for the Timing Optimization of Multilevel Logic," U.S. Pat. No. 5,282,148 (1994) describes an apparatus and method of synthesis of integrated circuits wherein logic decomposition is employed to optimize the timing of the circuits multilevel logic. The method realizes a layout for large scale integrated circuits having a plurality of gates after decomposing multiple input gates into a plurality of gate networks having a fewer number of inputs.